A key-value store is a data organization system where each “value” to be stored is associated with a unique “key.” The basic operations of a key-value store are insert and lookup commands. An insert command is issued to store the key-value pairs on the storage device. A lookup command is issued to retrieve the value associated with a specified key, if the key and value exist. A key-value system must be able to insert and look up key-value pairs in a time-efficient manner. Ideally, key-value pairs are stored and maintained in sorted order by key on the storage device. Algorithmically, inserting and looking up keys within a sorted sequence is substantially faster in time than performing the same operations on an unsorted sequence. In order to maintain a sequence of key-value pairs in sorted order, it is necessary to reorganize the existing data when new key-value pairs are being inserted.
However, as the size of key-value stores increase the maintaining efficiency of looking up a key and inserting a key becomes more challenging to maintain.
Caching may be used to store key-value stores for increased performance of a key-value store. Caching is the temporary storage of data for subsequent retrieval. Memory devices are often used to store data provided by a computer program. Examples of memory storage devices include, but are not limited to, solid-state drives, hard disk drives, and optical drives. These types of storage devices are inexpensive and hold large amounts of data. However, one tradeoff for their economic value is that they are slow compared to other components used in a computer. For example, a consumer hard drive can store terabytes of data cheaply, but has a maximum theoretical transfer rate of 300 megabytes (MB) per second. Random access memory (RAM) is faster in performance but higher in price, with a maximum theoretical transfer rate of 12.8 gigabytes (GB) per second. A central processing unit (CPU) with specialized memory known as level 1 (L1) cache or level 2 (L2) cache has even better performance but at an even higher price, with a transfer rate of 16 GB per second, or over fifty times faster than the storage device.
A technique known as caching may be used to increase, or accelerate, overall system performance. Caching may be used to store data requested from one component, into another component, to speed future requests for the same data. The data stored in a cache often may be values previously requested by a software application, by an operating system, or by another hardware component. Caching organizes a small amount of fast-access memory and a large amount of slow-access memory. The first time that a value is requested, the data is not in the cache, so the requested value is retrieved from the slow-access memory. In a cache, when the value is retrieved from the slow-access memory, the value is sent to the component that requested it, and the value also is stored in the fast-access memory for future requests. The next time that the same value is requested by the operating system or by any other program, the value is retrieved from the fast-access memory, with the result that the overall system performance is faster, or accelerated, by virtue of the value being available from the fast-access memory. By using faster memory components to cache data, more requests can be served from the cache instead of the slower storage device, and faster overall system performance is realized.
Key-value stores may be used to support fast retrieval and insertion of values to support numerous applications. Key-value stores may be implemented on numerous storage platforms which may or may not include cached platforms.